<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <!-- 
2、硬币
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
   -->
</head>
<body>
  <script>
      var backPack = function(m, A, V) {
    var dp = new Array(m+1).fill(0)// 动态规划数组，初始化值为0，即没有任何物品，价值为0
    // 外层循环物品
    for (var i = 0 ; i < A.length ; i++) {
        // 内层循环背包，倒序避免重复
        for (var j = m ; j>=0 ; j--) {
            if (j-A[i] >= 0) {
                // dp[j]表示公式里面的A(Y),V[i]表示pj,A[i]表示wj
                dp[j] = Math.max(dp[j],dp[j-A[i]]+V[i])
            }
        }
    }
    return dp[m]// 达到背包容量时，即最大价值
}
  </script>
</body>
</html>